# Darren
# 2025年02月22日09时00分47秒
# 层次建树
class Node:
    """
    节点类
    """

    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class Tree:
    """
    树类
    """

    def __init__(self):
        self.root = None
        self.queue = []

    def add_node(self, elem):
        """
        添加节点，建完全二叉树
        :param elem: 结点数据
        :return: None
        """
        new_node = Node(elem)
        self.queue.append(new_node)
        if not self.root:
            self.root = new_node
        else:
            if not self.queue[0].lchild:
                self.queue[0].lchild = new_node
            else:
                self.queue[0].rchild = new_node
                self.queue.pop(0)

    def pre_order(self, node: Node):
        """
        前序遍历
        """
        if node:
            print(node.elem, end=" ")
            self.pre_order(node.lchild)
            self.pre_order(node.rchild)

    def in_order(self, node: Node):
        """
        中序遍历
        """
        if node:
            self.in_order(node.lchild)
            print(node.elem, end=" ")
            self.in_order(node.rchild)

    def post_order(self, node: Node):
        """
        后序遍历
        """
        if node:
            self.post_order(node.lchild)
            self.post_order(node.rchild)
            print(node.elem, end=" ")

    def level_order(self):
        """
        层序遍历
        """
        node_queue = []
        node_queue.append(tree.root)
        while node_queue:
            node = node_queue.pop(0)
            print(node.elem, end=" ")
            if node.lchild:
                node_queue.append(node.lchild)
            if node.rchild:
                node_queue.append(node.rchild)


tree = Tree()
for i in range(1, 11):
    tree.add_node(i)
tree.pre_order(tree.root)
print('\n----------------------')
tree.in_order(tree.root)
print('\n----------------------')
tree.post_order(tree.root)
print('\n----------------------')
tree.level_order()
